package pl.edu.agh.agents.planner;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import pl.edu.agh.agents.agent.Agent;
import pl.edu.agh.agents.agent.ControlledAgent;
import pl.edu.agh.agents.agent.SystemManager;
import pl.edu.agh.agents.path.Path;
import pl.edu.agh.agents.state.Deadlock;
import pl.edu.agh.agents.state.State;
import pl.edu.agh.agents.state.StateSpace;

public class CentralPlanner extends Planner {
	private final static CentralPlanner plannerInstance = new CentralPlanner();
	private Map<Agent, Path> paths;
	private List<Agent> agents;
	private int lastAgentId = -15; // XXX wtf

	private List<Deadlock> deadlocks;
	private boolean deadlocksChecked = false;

	private List<Agent> dlAgents;
	private Map<Integer, List<Agent>> dlGroups;
	private Map<Agent, State> dlAgentDest;
	private Map<Agent, State> dlAgentEntr;
	private List<State> dlEntryStates;
	private List<Agent> dlAgentIN;
	private List<Agent> agentsMoving;

	public static CentralPlanner getInstance() {
		return plannerInstance;
	}

	private CentralPlanner() {
		agents = new ArrayList<Agent>();
		paths = new HashMap<Agent, Path>();
		agentsMoving = new ArrayList<Agent>();
		SystemManager manager = SystemManager.getInstance();
		List<Agent> smAgents = manager.getAgents();
		for (Agent a : smAgents) {
			paths.put(a, null);

			if (a instanceof ControlledAgent) {
				agents.add(a);
				agentsMoving.add(a);
			}
		}
	}

	public void reset(boolean explicitDeadlocks) {
		agents = new ArrayList<Agent>();
		paths = new HashMap<Agent, Path>();
		agentsMoving = new ArrayList<Agent>();
		SystemManager manager = SystemManager.getInstance();
		List<Agent> smAgents = manager.getAgents();
		for (Agent a : smAgents) {
			paths.put(a, null);

			if (a instanceof ControlledAgent) {
				agents.add(a);
				agentsMoving.add(a);
			}
		}

		lastAgentId = -15;
		deadlocksChecked = false;
		deadlocks = new ArrayList<Deadlock>();
		dlEntryStates = new ArrayList<State>();
		dlAgents = new ArrayList<Agent>();
		dlGroups = new HashMap<Integer, List<Agent>>();
		dlAgentDest = new HashMap<Agent, State>();
		dlAgentEntr = new HashMap<Agent, State>();
		dlAgentIN = new ArrayList<Agent>();
		
		if (explicitDeadlocks) {
			searchDeadlocks();
		}
	}

	public void addAgent(Agent agent) {
		if (!agents.contains(agent)) {
			agents.add(agent);
		}
	}

	public void removeAgent(Agent agent) {
		agents.remove(agent);
	}

	public void updatePath(Agent agent, Path path) {
		paths.remove(agent);
		paths.put(agent, path);
	}

	@Override
	public Path calculatePath(Agent agent) {
		Path p = null;
		// jak ida po sobie agenty planera to nie replanujemy
		if (((lastAgentId + 1) % agents.size() == agent.getID() && paths.get(agent) != null) || (lastAgentId == agent.getID() && agentsMoving.size() == 1)) {
			lastAgentId = agent.getID();
			p = paths.get(agent);
			p.remove(agent.getCurrentState());
			paths.put(agent, p);
		}
		p = checkPathForDeadlocks(agent, p);
		if (p == null || !p.validate()) {
			System.out.println("CP: Obliczam dla agenta " + agent.getID());
			Map<Agent, Path> myPaths = paths;
			Map<Agent, Path> shortestSolution = new HashMap<Agent, Path>();
			int shortestSize = Integer.MAX_VALUE;
			List<Agent> myAgents = new ArrayList<Agent>(agents);

			myAgents.remove(agent);
			myAgents.add(0, agent);

			int size = 0;
			int numberOfAgents = Math.max(1, myAgents.size() / 2);
			// numberOfAgents = 1;
			for (int i = 0; i < numberOfAgents; i++) {
				Collections.shuffle(myAgents);
				//jak agent musi isc to wyznaczamy najlepsze rozwiazanie dla niego
				if (agentMustGo(agent)) {
					myAgents.remove(agent);
					myAgents.add(0, agent);
				}

				size = 0;
				myPaths = new HashMap<Agent, Path>();
				for (Agent a : myAgents) {

					Path path = null;
					if (dlAgents.contains(a)) {
						path = calculateDeadlockPath(a);
					} else {
						path = calculatePath(a, myPaths, true, dlEntryStates);
					}

					myPaths.put(a, path);
					if (myPaths.get(a) != null) {
						size += myPaths.get(a).size();
					} else {
						size += Integer.MAX_VALUE / agents.size();
					}
				}

				if (size < shortestSize) {
					shortestSize = size;
					shortestSolution.clear();
					shortestSolution.putAll(myPaths);
				}
			}

			setPaths(shortestSolution);
		}
		
		return paths.get(agent);
	}

	private void setPaths(Map<Agent, Path> newPaths) {
		for (Agent agent : newPaths.keySet()) {
			if (dlAgents.contains(agent)) {
				if (newPaths.get(agent) != null && newPaths.get(agent).get(0).equals(dlAgentDest.get(agent))) {
					dlAgents.remove(agent);
					dlAgentIN.remove(agent);
				} else if (newPaths.get(agent) != null && newPaths.get(agent).get(0).equals(dlAgentEntr.get(agent))) {
					for (Deadlock d : deadlocks) {
						if (d.starts(dlAgentEntr.get(agent))) {
							for (State state : d.getStates()) {
								if (!state.isEmpty()) {
									Agent a = state.getAgent();
									if (!agentsInTheSameGroup(agent, a)) {
										Path oldPath = newPaths.get(agent);
										Path agentPath = new Path();
										agentPath.add(agent.getCurrentState());
										agentPath.add(oldPath.get(0));
										newPaths.put(agent, agentPath);
										break;
									}
								}
							}

						}
					}
					dlAgentIN.add(agent);
				}
			}
		}
		paths.putAll(newPaths);
	}

	private Path calculateDeadlockPath(Agent agent) {
		if (dlAgentIN.contains(agent)) {
			return getBestPath(agent.getCurrentState(), dlAgentDest.get(agent));
		}
		Path path = calculatePath(agent, dlAgentDest.get(agent), paths, true, dlEntryStates);
		if (path != null && path.get(0).equals(dlAgentEntr.get(agent))) {
			for (Deadlock d : deadlocks) {
				if (d.starts(dlAgentEntr.get(agent))) {
					for (State state : d.getStates()) {
						if (!state.isEmpty()) {
							Agent a = state.getAgent();
							if (!agentsInTheSameGroup(agent, a)) {
								Path oldPath = path;
								path = new Path();
								path.add(agent.getCurrentState());
								path.add(oldPath.get(0));
								break;
							}
						}
					}

				}
			}
		}
		return path;
	}

	public boolean agentMustGo(Agent agent) {
		for (Deadlock d : deadlocks) {
			if (d.starts(agent.getCurrentState())) {
				return true;
			}
		}
		return false;
	}

	private Path checkPathForDeadlocks(Agent agent, Path path) {
		if (path != null && path.size() > 0) {
			for (Deadlock d : deadlocks) {
				if (d.starts(path.get(0))) {
					if (path.size() > 1 && !d.contain(path.get(1))) {
						break;
					}
					for (State state : d.getStates()) {
						if (!state.isEmpty()) {
							Agent a = state.getAgent();
							if (!agentsInTheSameGroup(agent, a)) {
								paths.put(agent, null);
							}
						}
					}

				}
			}
		} else {
			paths.put(agent, null);
		}
		return paths.get(agent);
	}

	private boolean agentsInTheSameGroup(Agent a1, Agent a2) {
		for (List<Agent> list : dlGroups.values()) {
			if (list.contains(a1) && list.contains(a2)) {
				return true;
			}
		}
		return false;
	}

	public boolean waitBeforeDeadlock(Agent agent, int iteration, State s) {
		Path path = paths.get(agent);
		if (path != null) {
			for (Deadlock d : deadlocks) {
				if (d.starts(path.get(0))) {
					for (State state : d.getStates()) {
						if (!state.isEmpty()) {
							Agent a = state.getAgent();
							if (a.getPath() == null || a.getPath().size() <= iteration || a.getPath().get(iteration) == null
									|| d.myDirection(state, a.getPath().get(iteration), path.get(0))) {
								return true;
							}
						}
					}
				}
			}
		}
		return false;
	}

	private void searchDeadlocks() {
		if (!deadlocksChecked) {
			List<State> states = space.getStates();
			for (State s : states) {
				if (s.getNeighbors().size() > 1) {
					for (State n : s.getNeighbors()) {
						if (n.getNeighbors() != null
								&& (n.getNeighbors().size() == 1 || (n.getNeighbors().size() == 2 && (n.getNeighbors().get(0).equals(s) || n.getNeighbors()
										.get(1).equals(s))))) {
							Deadlock d = new Deadlock(deadlocks.size());
							d.setStartOrEnd(s);
							d.put(s);
							State prevn = s;
							while (n.getNeighbors().size() < 3) {
								if (n.getNeighbors() == null || n.getNeighbors().isEmpty()) {
									break;
								}
								if (n.getNeighbors().size() == 2 && !(n.getNeighbors().get(0).equals(s) || n.getNeighbors().get(1).equals(prevn))) {
									break;
								}
								d.put(n);
								State temp = n;
								if (n.getNeighbors().size() == 2) {
									if (n.getNeighbors().get(0).equals(prevn)) {
										n = n.getNeighbors().get(1);
									} else {
										n = n.getNeighbors().get(0);
									}
								} else {
									n = n.getNeighbors().get(0);
								}
								prevn = temp;
							}
							d.setStartOrEnd(n);
							d.put(n);
							boolean is = false;
							for (Deadlock dead : deadlocks) {
								if(dead.contains(d)){
									is=true;
									break;
								}
							}
							if (!is && d.size() > 3) {
								deadlocks.add(d);
								dlEntryStates.add(d.getBegin());
								dlEntryStates.add(d.getEnd());
							}
						}
					}
				}
			}
			deadlocksChecked = true;
			reorganizeDeadlocks();
			checkAgentsPathsForDeadlocks();
		}
		if (deadlocks.size() > 0) {
			System.out.println("Deadlocks size: " + deadlocks.size());
		}
		for (Deadlock de : deadlocks) {
			System.out.println(de.toString());
		}
	}
	
	private void reorganizeDeadlocks(){
		// TODO
		List<Deadlock> newDeadlocks = new ArrayList<Deadlock>();
		Set<Deadlock> deadlocksToRemove = new HashSet<Deadlock>();
		for (Deadlock d1 : deadlocks) {
			for (Deadlock d2 : deadlocks) {
				if(!d1.contains(d2)){
					if(d2.starts(d1.getBegin()) || d2.starts(d1.getEnd())){
						boolean start;
						State joinState = null;
						if(d2.starts(d1.getBegin())){
							start = false;
							joinState = d1.getBegin();
						} else {
							start = true;
							joinState = d1.getEnd();
						}
						Deadlock d = new Deadlock(deadlocks.size() + newDeadlocks.size());
						if(start){
							d.setStartOrEnd(d1.getEnd(joinState));
							d.setStartOrEnd(d2.getEnd(joinState));
							if(d1.getBegin().equals(joinState)){
								List<State> list = d1.getStates();
								Collections.reverse(list);
								d.put(list);
							} else {
								d.put(d1.getStates());
							}
							d.remove(d.size()-1);
							d.put(d2.getStates());
							
						} else {
							d.setStartOrEnd(d2.getEnd(joinState));
							d.setStartOrEnd(d1.getEnd(joinState));
							if(d2.getBegin().equals(joinState)){
								List<State> list = d2.getStates();
								Collections.reverse(list);
								d.put(list);
							} else {
								d.put(d2.getStates());
							}
							d.remove(d.size()-1);
							d.put(d1.getStates());
						}
						boolean is = false;
						for (Deadlock dead : newDeadlocks) {
							if(dead.contains(d)){
								is=true;
								break;
							}
						}
						Path dlStates = new Path(d.getStates());
						if(!is && dlStates.simpleValidation()){
							newDeadlocks.add(d);
						}

						deadlocksToRemove.add(d1);
						deadlocksToRemove.add(d2);
					}
				}
			}
		}
		deadlocks.removeAll(deadlocksToRemove);
		deadlocks.addAll(newDeadlocks);
	}

	private void checkAgentsPathsForDeadlocks() {
		for (Agent a : agentsMoving) {
			Path path = a.getBestPath();
			Deadlock d = isDeadlockInPath(path);
			if (d != null) {
				if (path.indexOf(d.getBegin()) < path.indexOf(d.getEnd())) {
					assignAgentToGroup(a, d.getBegin(), d.getEnd());
				} else {
					assignAgentToGroup(a, d.getEnd(), d.getBegin());
				}
				dlAgents.add(a);
			}
		}
	}

	/**
	 * Sprawdzanie czy agent ma na sciezce waskie gardlo
	 */
	private Deadlock isDeadlockInPath(Path path) {
		if (path == null) {
			return null;
		}
		for (Deadlock d : deadlocks) {
			// TODO - check
			if (path.contains(d.getBegin()) && path.contains(d.getEnd())) {
				return d;
			}
		}
		return null;
	}

	private void assignAgentToGroup(Agent agent, State begin, State end) {
		for (int i : dlGroups.keySet()) {
			Agent a = dlGroups.get(i).get(0);
			Algorithm alg = StateSpace.getInstance().getAlgorithm();
			Path path = alg.calculatePath(agent.getCurrentState(), a.getCurrentState());
			Deadlock d = isDeadlockInPath(path);
			if (d == null) {// &&
							// groupOfAgentDeadlockBeginigMap.get(i).equals(state)){
				List<Agent> list = dlGroups.get(i);
				list.add(agent);
				dlAgentDest.put(agent, end);
				dlAgentEntr.put(agent, begin);
				dlGroups.put(i, list);
				return;
			}
		}

		List<Agent> list = new ArrayList<Agent>();
		list.add(agent);
		dlAgentDest.put(agent, end);
		dlAgentEntr.put(agent, begin);
		dlGroups.put(dlGroups.size(), list);
	}

	public void agentInGoalState(Agent agent) {
		agentsMoving.remove(agent);
	}
}
